1437. Check If All 1's Are at Least Length K Places Away

Easy

題目描述

Description

Given an binary array nums and an integer k, return true if all 1's are at least k places away from each other, otherwise return false.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Constraints:

• 1 $\le$ nums.length $\le$ $10^5$
• 0 <= k <= nums.length
• nums[i] is 0 or 1

解答

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var kLengthApart = function (nums, k) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 1) {
      for (let j = 1; j <= k; j++) {
        if (nums[i + j] === 1) {
          return false;
        }
      }
    }
  }

  return true;
};

解題思路

把題目描述轉成 JS 程式碼，先是遍歷迴圈，當遇到該格是 1 的時候就檢查往前 k 格之內有沒有其他的 1，若有則 false，若遍歷完一遍後皆沒有則 true。

心得

我的解法用了兩個 for 迴圈，時間複雜度變成 O($n^2$) 不太好，應該可以再簡化